import java.util.ArrayList;
import java.util.List;

/**
 * Created by losor on 2017/3/6.
 */
//重点

public class _448_FindAllNumbersDisappearedInAnArray {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> outLits = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            //将每个数值转换成index的下标
            int index = Math.abs(nums[i] )-1;
            if (nums[index]>0){
                //如果这个没有达到过,则取反，用来标记一下是否遍历到过
                nums[index] = -nums[index];
            }
        }

        for (int i = 0; i < nums.length; i++) {
            //如果大于0，说明之前的是偶没有遍历到过这个i值
            if(nums[i]>0){
                outLits.add(i+1);
            }
        }
        return outLits;
    }

}
